The present invention relates to a method and apparatus for scheduling execution units of parallel processing in a multiprocessor system.
Recent operating systems that support multitasking realize a multitasking environment in which a plurality of processes can be executed simultaneously, and implement a multithread technology by which these processes can generate a plurality of threads inside the processes allowing for parallel processing. Processes are allocated unique resources or address spaces at the time of execution, and are incapable of accessing the areas of the other processes. In contrast, threads are execution units generated inside the processes, and each thread can access the areas of the other threads freely within its own process. Threads are the basic execution units for an operating system to allocate CPU (Central Processing Unit) execution time to. As employed herein, thread allocation will be referred to as scheduling.
A multiprocessor system, or a system that implements a plurality of processors, can perform processing in parallel or in a cooperative fashion to achieve speedup of the entire processing. In multiprocessor systems, executable threads are usually retained in a queue called a task queue on a shared memory. These threads are allocated to any of the processors for execution. Since the process execution speed, the memory consumption, and other performance depend upon the method of thread allocation, multiprocessor systems require some contrivance that is different from the scheduling used in single-processor systems.
In a possible example of the scheduling method used in a multiprocessor system, a management unit in charge of managing threads may communicate with individual processors and schedule threads to be allocated to the respective processors.
This method in which the management unit performs scheduling has the problem that communication between the management unit and the processors often cause a message delay and can delay the execution of the threads. Among the possible solutions to this problem is a method in which each individual processor performs scheduling in an autonomous fashion. In this method, the processors run respective schedulers thereon and access a task queue on a shared memory to select threads to execute.
According to this method, each processor locks the task queue while executing its scheduler, i.e., during scheduling, so as to prevent the task queue on the shared memory from being modified by the other processors. This puts system designers in a dilemma as to whether or not to disable interrupts in the meantime.
If interrupts are not disabled during scheduling, the interrupts can be accepted while the task queue is locked by a scheduler. In this case, scheduling will not be performed until the interrupt processing ends and the task queue is unlocked, resulting in a reduction in system efficiency.
Conversely, if interrupts are disabled during scheduling, the problem occurs where the system drops in interrupt response. These problems are not only associated with kernel schedulers which run on the multiprocessors described so far, but also apply to user-level schedulers in a multiprocessor multithreading environment (that is, a mode where schedulers are executed on threads running on the respective processors so that multithreading is achieved at the user level).
In particular, since kernel threads that execute the user-level schedulers are scheduled by kernel-level schedulers on the respective processors and thus have the possibility of being preempted by other kernel threads, the locking of the task queue may cause more serious problems. In this case, if a kernel thread is preempted while the user-level scheduler running thereon is locking, then the user-level schedulers running on threads of the other processors cannot perform scheduling until the lock is released.